home *** CD-ROM | disk | FTP | other *** search
/ ftp.mactech.com 2010 / ftp.mactech.com.tar / ftp.mactech.com / challenge / 13.08 / ChallengeEqEval.sit.hqx / Challenge, Equation Evaluator / Evaluate.c < prev    next >
Text File  |  1997-06-25  |  15KB  |  723 lines
  1. //
  2. //    Evaluate.c
  3. //
  4. //    MacTech Programmer's Challenge entry for May, 1997
  5. //    Written by Mark Day
  6. //
  7. //    Contains routines to parse an equation and drive the
  8. //    evaluation of that equation over a set of input values.
  9.  
  10.  
  11. #include <ctype.h>
  12. #include <string.h>
  13. #include <math.h>
  14. #undef HUGE_VAL                        // fp.h redefines this
  15. #include <fp.h>
  16. #include <Memory.h>
  17. #include <OSUtils.h>
  18. #include "Evaluate.h"
  19.  
  20.  
  21. ulong gVariableFlags;
  22.  
  23.  
  24. struct TokenLookup {
  25.     int        token;
  26.     int        which;
  27.     char    *string;
  28. };
  29. typedef struct TokenLookup TokenLookup;
  30.  
  31. TokenLookup gTokenLookup[] = {
  32.     tokLeftParen,    kLeftParen,        "(",
  33.     tokRightParen,    kRightParen,    ")",
  34.     tokAddOp,        kAdd,            "+",
  35.     tokAddOp,        kSubtract,        "-",
  36.     tokMulOp,        kMultiply,        "*",
  37.     tokMulOp,        kDivide,        "/",
  38.     tokPowerOp,        kExponent,        "^",
  39.     tokRootOp,        kFuncSquareRoot,"\\",
  40.     tokFactorial,    kFuncFactorial,    "!",
  41.     tokFunction,    kFuncLogN,        "ln",
  42.     tokFunction,    kFuncLogTen,    "log",
  43.  
  44.     //    Hyperbolic functions need to come first or else they
  45.     //    would parse as the normal functions plus an extra
  46.     //    "h" character (which makes for a syntax error)
  47.     tokFunction,    kFuncSinh,        "sinh",
  48.     tokFunction,    kFuncCosh,        "cosh",
  49.     tokFunction,    kFuncTanh,        "tanh",
  50.     tokFunction,    kFuncSech,        "sech",
  51.     tokFunction,    kFuncCsch,        "csch",
  52.     tokFunction,    kFuncCoth,        "coth",
  53.     
  54.     tokFunction,    kFuncSin,        "sin",
  55.     tokFunction,    kFuncCos,        "cos",
  56.     tokFunction,    kFuncTan,        "tan",
  57.     tokFunction,    kFuncSec,        "sec",
  58.     tokFunction,    kFuncCsc,        "csc",
  59.     tokFunction,    kFuncCot,        "cot",
  60.  
  61.     tokFunction,    kFuncArcSin,    "asin",
  62.     tokFunction,    kFuncArcCos,    "acos",
  63.     tokFunction,    kFuncArcTan,    "atan",
  64.     tokFunction,    kFuncArcSec,    "asec",
  65.     tokFunction,    kFuncArcCsc,    "acsc",
  66.     tokFunction,    kFuncArcCot,    "acot",
  67.  
  68.     tokFunction,    kFuncAbs,        "abs",
  69.  
  70.     tokVariable,    kPi,            "p",
  71.     tokVariable,    kE,                "e",
  72.     tokVariable,    kR,                "r",
  73.     tokVariable,    kTheta,            "t",
  74.     tokVariable,    kX,                "x",
  75.     tokVariable,    kY,                "y",
  76.     tokVariable,    kZ,                "z",
  77.     tokVariable,    kN,                "n",
  78.     tokAssign,        kEquals,        "=",
  79.     tokInvalid,        kInvalidToken,    "",
  80. };
  81.  
  82. //
  83. //    These are single precision versions of functions, not
  84. //    found in either math.h or fp.h
  85. //
  86. static float Factorial(float x) { return gamma(x+1.0); }
  87. static float Secant(float x) { return 1.0 / cosf(x); }
  88. static float CoSecant(float x) { return 1.0 / sinf(x); }
  89. static float CoTangent(float x) { return 1.0 / tanf(x); }
  90. static float ArcSecant(float x) { return acosf(1.0/x); }
  91. static float ArcCoSecant(float x) { return asinf(1.0/x); }
  92. static float ArcCoTangent(float x) { return atanf(1.0/x); }
  93. static float HypSecant(float x) { return 1.0 / coshf(x); }
  94. static float HypCoSecant(float x) { return 1.0 / sinhf(x); }
  95. static float HypCoTangent(float x) { return 1.0 / tanhf(x); }
  96.  
  97. typedef float (*FloatFunc)(float);
  98. FloatFunc    gFunctions[] = {
  99.     (FloatFunc) powf,
  100.     fabsf,
  101.     sqrtf,
  102.     Factorial,
  103.     expf,
  104.     logf,
  105.     log10f,
  106.     
  107.     sinf,
  108.     cosf,
  109.     tanf,
  110.     Secant,
  111.     CoSecant,
  112.     CoTangent,
  113.     
  114.     asinf,
  115.     acosf,
  116.     atanf,
  117.     ArcSecant,
  118.     ArcCoSecant,
  119.     ArcCoTangent,
  120.     
  121.     sinhf,
  122.     coshf,
  123.     tanhf,
  124.     HypSecant,
  125.     HypCoSecant,
  126.     HypCoTangent,
  127.     
  128.     (FloatFunc) atan2f
  129. };
  130.  
  131.  
  132. //
  133. //    Return the next token in the equation.  Adjust the
  134. //    pointer to point just after the token.
  135. //
  136. int GetToken(char **equation, Constant *value)
  137. {
  138.     int            token = tokInvalid;
  139.     char        *s = *equation;
  140.     int            i;
  141.     int            width;
  142.     TokenLookup    *p;
  143.     
  144.     //
  145.     //    skip leading white space
  146.     //
  147.     while (*s == ' ' || *s == '\t' || *s == '\n')
  148.         ++s;
  149.     
  150.     if (*s == '\0')
  151.         return tokInvalid;
  152.  
  153.     //
  154.     //    See if *s matches one of the token strings
  155.     //
  156.     p = gTokenLookup;
  157.     while (p->token != tokInvalid) {
  158.         char *tokenString = p->string;
  159.         size_t len = strlen(tokenString);
  160.         
  161.         if (!strncmp(s, tokenString, len)) {
  162.             token = p->token;
  163.             value->which = p->which;
  164.             s += len;
  165.             break;
  166.         }
  167.         else {
  168.             ++p;
  169.         }
  170.     }
  171.  
  172.     //
  173.     //    Update the current position within the string.
  174.     //
  175.     *equation = s;
  176.  
  177.     //
  178.     //    Try to parse a numeric constant.
  179.     //
  180.     if (token == tokInvalid) {
  181.         token = GetNumberToken(equation, value);
  182.     }
  183.     
  184.     
  185.     return token;
  186. }
  187.  
  188.  
  189. //
  190. //    GetNumberToken recognizes numeric constants of the forms
  191. //    [0-9]+.[0-9]*  or  [0-9]*.[0-9]+
  192. //
  193. int GetNumberToken(char **equation, Constant *value)
  194. {
  195.     char    *s;
  196.     char    c;                //    keep the next character in a register
  197.     long    digits = 0;        //    used to determine whether we've seen any digits yet
  198.     float    val;            //    the value of the constant
  199.     float    divisor;        //    keeps track of place value of float digits
  200.     int        token;            //    the kind of number we found
  201.     
  202.     token = tokInvalid;        //    assume we didn't find a number
  203.     s = *equation;            //    point to start of string
  204.     c = *s;                    //    get first char
  205.     
  206.     //
  207.     //    Gather the integer part of the constant
  208.     //
  209.     val = 0.0;
  210.     while (isdigit(c)) {
  211.         val = val * 10.0 + (c - '0');    //    shift in the next digit
  212.         ++digits;                        //    remember we found a digit
  213.         c = *(++s);                        //    get next character
  214.     }
  215.     
  216.     //
  217.     //    If we found an integer part, prepare to return it.
  218.     //
  219.     if (digits) {
  220.         value->f = val;
  221.         token = tokFloat;
  222.     }
  223.     
  224.     //
  225.     //    Now let's see if there is a trailing decimal point
  226.     //    and optional digits.  If so, then this is a floating
  227.     //    point constant.
  228.     //
  229.     if (c == '.') {
  230.         c = *(++s);                            //    skip over decimal point
  231.         divisor = 1.0;                        //    haven't seen fraction part yet
  232.         
  233.         while (isdigit(c)) {
  234.             val = val * 10.0 + (c - '0');    //    shift in next digit
  235.             divisor *= 10;                    //    remember to fix place value
  236.             ++digits;                        //    we saw another digit
  237.             c = *(++s);                        //    get next character
  238.         }
  239.         
  240.         //
  241.         //    If there were digits before or after the decimal
  242.         //    point, then we have a valid float.  Otherwise,
  243.         //    we only saw a decimal point.
  244.         //
  245.         if (digits) {
  246.             value->f = val / divisor;        //    this fixes the place value
  247.             token = tokFloat;
  248.         }
  249.         else {
  250.             //    We saw only a decimal point.  Point us back at the decimal point.
  251.             --s;
  252.         }
  253.     }
  254.     
  255.     *equation = s;                            //    point beyond what we found
  256.     return token;                            //    return what we found
  257. }
  258.  
  259.  
  260. TokenNode *NewTokenNode(TokenNode *left, TokenNode *right, int token)
  261. {
  262.     TokenNode    *node;
  263.     node = (TokenNode *) NewPtr(sizeof(TokenNode));
  264.     node->left = left;
  265.     node->right = right;
  266.     node->token = token;
  267.     
  268.     return node;
  269. }
  270.  
  271. void FreeTree(TokenNode *root)
  272. {
  273.     if (root) {
  274.         FreeTree(root->left);
  275.         FreeTree(root->right);
  276.         DisposePtr((Ptr) root);
  277.     }
  278. }
  279.  
  280. /*
  281.     A simple parser for our expression grammar.  The grammar
  282.     looks like:
  283.     
  284.     expression    ->    term  ( ADD_OP  term )*
  285.     term        ->    factor  ( [ MULTIPLY_OP ]  factor )*
  286.     factor        ->    SQUARE_ROOT  factor
  287.                 |    signed  EXPONENT  factor
  288.                 |    signed
  289.     signed        ->    MINUS  signed
  290.                 |    PLUS  signed
  291.                 |    gamma
  292.     gamma        ->    simple_value  ( FACTORIAL )*
  293.     simple_value->    NUMBER
  294.                 |    VARIABLE
  295.                 |    LEFT_PAREN  expression  RIGHT_PAREN
  296.                 |    FUNCTION   LEFT_PAREN  expression  RIGHT_PAREN
  297.     statement    ->    VARIABLE  EQUALS  expression
  298.     
  299.     where (...)* means repeated zero or more times, and
  300.     [...] means optional.
  301. */
  302.  
  303. TokenNode *ParseExpression(char **s)
  304. {
  305.     char        *temp;
  306.     TokenNode    *left, *right, *node;
  307.     int            token;
  308.     Constant    value;
  309.     
  310.     node = NULL;
  311.     
  312.     //    Get the first term
  313.     left = ParseTerm(s);
  314.     if (left == NULL)
  315.         return left;
  316.     node = left;
  317.  
  318.     //    Get successive terms, separated by tokAddOp's
  319.     do {
  320.         temp = *s;
  321.         token = GetToken(&temp, &value);
  322.         if (token == tokAddOp) {
  323.             *s = temp;
  324.             right = ParseTerm(s);
  325.             if (right) {
  326.                 node = NewTokenNode(left, right, token);
  327.                 node->value.which = value.which;
  328.                 left = node;        //    this makes it left-associative
  329.             }
  330.         }
  331.     } while (token == tokAddOp);
  332.     
  333.     return node;
  334. }
  335.  
  336. TokenNode *ParseTerm(char **s)
  337. {
  338.     char        *temp;
  339.     TokenNode    *left, *right, *node;
  340.     int            token;
  341.     Constant    value;
  342.     
  343.     node = NULL;
  344.     
  345.     left = ParseFactor(s);
  346.     if (left == NULL)
  347.         return left;
  348.     node = left;
  349.     
  350.     //
  351.     //    Get successive factors.  They may be separated by
  352.     //    tokMulOp's, or they may be adjacent (implying
  353.     //    multiplication).  If we find a tokAddOp, then we
  354.     //    have to unwind; otherwise, an expression like
  355.     //    "3 - 7" would be parsed as "3 * (-7)".
  356.     //
  357.     
  358.     do {
  359.         temp = *s;
  360.         token = GetToken(&temp, &value);
  361.         switch (token) {
  362.             //    Explicit multiply/divide
  363.             case tokMulOp:
  364.                 *s = temp;
  365.                 right = ParseFactor(s);
  366.                 if (right) {
  367.                     node = NewTokenNode(left, right, token);
  368.                     node->value.which = value.which;
  369.                     left = node;    // this makes it left-associative
  370.                 }
  371.                 break;
  372.             
  373.             //    Explicit add/subtract; don't do implicit multiply.
  374.             //    Use the single factor only.
  375.             case tokAddOp:
  376.                 node = left;
  377.                 break;
  378.  
  379.             //    Implicit multiply or single factor
  380.             default:
  381.                 //    Try to find a second factor
  382.                 temp = *s;
  383.                 right = ParseFactor(s);
  384.                 if (right) {
  385.                     //    Got one, so do implicit multiply
  386.                     token = tokMulOp;    //    pretend there was an explicit multiply
  387.                     node = NewTokenNode(left, right, token);
  388.                     node->value.which = kMultiply;
  389.                     left = node;    // make it left-associative
  390.                 }
  391.                 else {
  392.                     //    Nope, just a single factor
  393.                     *s = temp;        // put back the tokens ParseFactor gobbled
  394.                     node = left;
  395.                 }
  396.                 break;
  397.         }
  398.     } while (token == tokMulOp);    
  399.     
  400.     return node;
  401. }
  402.  
  403. TokenNode *ParseFactor(char **s)
  404. {
  405.     char        *temp;
  406.     TokenNode    *left, *right, *node;
  407.     int            token;
  408.     Constant    value;
  409.  
  410.     node = NULL;
  411.     
  412.     //
  413.     //    See if this is a (unary) square root
  414.     //
  415.     temp = *s;
  416.     token = GetToken(&temp, &value);
  417.     if (token == tokRootOp) {
  418.         *s =temp;
  419.         left = ParseFactor(s);
  420.         if (left) {
  421.             //    square root is evaluated as a function call
  422.             node = NewTokenNode(left, NULL, tokFunction);
  423.             node->value.which = kFuncSquareRoot;
  424.         }
  425.         return node;
  426.     }
  427.     
  428.     //
  429.     //    If we get here, it's either "negative EXPONENT factor" or "negative"
  430.     //
  431.     left = ParseNegative(s);
  432.     if (left == NULL)
  433.         return left;
  434.  
  435.     temp = *s;
  436.     token = GetToken(&temp, &value);
  437.     if (token == tokPowerOp) {
  438.         *s = temp;
  439.         right = ParseFactor(s);
  440.         if (right) {
  441.             //    We've found u ^ v.  If u == e, then convert it to
  442.             //    a function call, exp(v).
  443.             if (left->token == tokVariable && left->value.which == kE) {
  444.                 node = left;        // re-use the node for left
  445.                 node->token = tokFunction;
  446.                 node->value.which = kFuncExp;
  447.                 node->left = right;    // set up the function argument
  448.             }
  449.             else {
  450.                 //    It's an ordinary power, so build a node for it.
  451.                 node = NewTokenNode(left, right, token);
  452.                 node->value.which = value.which;
  453.             }
  454.         }
  455.     }
  456.     else {
  457.         node = left;
  458.     }
  459.     
  460.     return node;
  461. }
  462.  
  463. TokenNode *ParseNegative(char **s)
  464. {
  465.     char        *temp;
  466.     TokenNode    *left, *node;
  467.     int            token;
  468.     Constant    value;
  469.  
  470.     node = NULL;
  471.     left = NULL;
  472.     
  473.     //
  474.     //    See if this is minus gamma, or gamma.
  475.     //
  476.     temp = *s;
  477.     token = GetToken(&temp, &value);
  478.     if (token == tokAddOp && value.which == kSubtract) {
  479.         *s =temp;
  480.         left = ParseNegative(s);
  481.         if (left) {
  482.             node = NewTokenNode(left, NULL, tokNegate);
  483.             node->value.which = value.which;
  484.         }
  485.     }
  486.     else {
  487.         node = ParseFactorial(s);
  488.     }
  489.     
  490.     return node;
  491. }
  492.  
  493. TokenNode *ParseFactorial(char **s)
  494. {
  495.     char        *temp;
  496.     TokenNode    *left, *node;
  497.     int            token;
  498.     Constant    value;
  499.  
  500.     //
  501.     //    First, get a simple value.
  502.     //
  503.     left = ParseSimpleValue(s);
  504.     if (left == NULL)
  505.         return left;
  506.     node = left;
  507.     
  508.     //
  509.     //    Gather trailing !'s
  510.     //
  511.     do {
  512.         temp = *s;
  513.         token = GetToken(&temp, &value);
  514.         if (token == tokFactorial) {
  515.             *s = temp;
  516.             //    The factorial operator is converted to a
  517.             //    function call to the factorial function.
  518.             node = NewTokenNode(left, NULL, tokFunction);
  519.             node->value.which = kFuncFactorial;
  520.             left = node;
  521.         }
  522.     } while (token == tokFactorial);
  523.     
  524.     return node;
  525. }
  526.  
  527. TokenNode *ParseSimpleValue(char **s)
  528. {
  529.     char        *temp;
  530.     TokenNode    *node, *left;
  531.     int            token;
  532.     Constant    value;
  533.  
  534.     left = NULL;
  535.     node = NULL;
  536.     
  537.     temp = *s;
  538.     token = GetToken(s, &value);
  539.     switch (token) {
  540.         case tokFloat:
  541.             left = NewTokenNode(NULL, NULL, token);
  542.             left->value = value;
  543.             ++gNumConstants;
  544.             break;
  545.  
  546.         case tokVariable:
  547.             left = NewTokenNode(NULL, NULL, token);
  548.             left->value = value;
  549.             switch (value.which) {
  550.                 case kPi:
  551.                     gVariableFlags |= kPiMask;
  552.                     break;
  553.                 case kE:
  554.                     gVariableFlags |= kEMask;
  555.                     break;
  556.                 case kR:
  557.                     //    using r implies using x and y since
  558.                     //    r is computed from x and y
  559.                     gVariableFlags |= kRMask + kXMask + kYMask;
  560.                     break;
  561.                 case kTheta:
  562.                     //    using theta implies using x and y
  563.                     //    since theta is computed from x and y
  564.                     gVariableFlags |= kThetaMask + kXMask + kYMask;
  565.                     break;
  566.                 case kX:
  567.                     gVariableFlags |= kXMask;
  568.                     break;
  569.                 case kY:
  570.                     gVariableFlags |= kYMask;
  571.                     break;
  572.                 case kN:
  573.                     gVariableFlags |= kNMask;
  574.                     break;
  575.             }
  576.             break;
  577.             
  578.         case tokFunction:
  579.             node = NewTokenNode(NULL, NULL, token);
  580.             node->value.which = value.which;
  581.             
  582.             //
  583.             //    If the function was abs(), then convert to a 
  584.             //    special token so it can be evaluated more
  585.             //    efficiently.
  586.             //
  587.             if (value.which == kFuncAbs)
  588.                 node->token = tokAbs;
  589.  
  590.             token = GetToken(s, &value);
  591.             if (token != tokLeftParen) {
  592.                 //    Missing left parenthesis
  593.                 node = NULL;
  594.             }
  595.             //    Fall into processing of parethesized expression
  596.             
  597.         case tokLeftParen:
  598.             left = ParseExpression(s);
  599.             token = GetToken(s, &value);    // swallow right parenthesis
  600.             break;
  601.         
  602.         case tokRightParen:
  603.             //    A right parenthesis means we're doing doing
  604.             //    a recursive parse of an expression.  In that
  605.             //    case, pretend like we hit the end of string.
  606.             *s = temp;        //    back up so caller finds right parenthesis
  607.             break;
  608.  
  609.         case tokInvalid:
  610.             break;
  611.             
  612.         default:
  613.             //    An unexpected token was seen
  614.             break;
  615.     }
  616.  
  617.     //
  618.     //    If it was a function call, then point to the argument.
  619.     //    
  620.     if (node == NULL)
  621.         node = left;
  622.     else
  623.         node->left = left;
  624.  
  625.     return node;
  626. }
  627.  
  628. TokenNode *ParseStatement(char **s)
  629. {
  630.     TokenNode    *node, *left, *right;
  631.     int            token;
  632.     Constant    value;
  633.  
  634.     //
  635.     //    Get the variable
  636.     //
  637.     token = GetToken(s, &value);
  638.     if (token == tokVariable) {
  639.         left = NewTokenNode(NULL, NULL, token);
  640.         left->value = value;
  641.         if (value.which == kZ)
  642.             gVariableFlags |= kFunctionOfY;        // "z=" implies yP is valid input
  643.     }
  644.     
  645.     //
  646.     //    Get the assignment token
  647.     //
  648.     token = GetToken(s, &value);
  649.     if (token != tokAssign) {
  650.         //    Missing "="
  651.         return NULL;
  652.     }
  653.     
  654.     //
  655.     //    Get the expression
  656.     //
  657.     right = ParseExpression(s);
  658.     
  659.     //
  660.     //    Build the node
  661.     //
  662.     if (right) {
  663.         node = NewTokenNode(left, right, token);
  664.         node->value.which = value.which;
  665.     }
  666.     else {
  667.         node = NULL;
  668.     }
  669.     
  670.     return node;
  671. }
  672.  
  673. //
  674. //    Here's the main entry point for the challenge.
  675. //
  676. void Evaluate(
  677.     char            *equation,    // null-terminated equation to evaluate
  678.     const Values    *xP,        // input values for x
  679.     const Values    *yP,        // input values for y
  680.     const IntValues    *nP,        // input values for n
  681.     Results            w[])        // preallocated storage for equation values
  682. {
  683.     char        *s = equation;
  684.     TokenNode    *root;
  685.     Values        nFloatValues;
  686.     
  687.     //
  688.     //    Set up the floating point values of n
  689.     //
  690.     nFloatValues.first = nP->first;
  691.     nFloatValues.delta = nP->delta;
  692.     nFloatValues.howMany = nP->howMany;
  693.     
  694.     //
  695.     //    Parse the input equation
  696.     //
  697.     gVariableFlags = 0;
  698.     root = ParseStatement(&s);
  699.  
  700.     //
  701.     //    Generate code to evaluate the equation
  702.     //
  703.     CodeGen(root->right);
  704.     MakeDataExecutable(gCodeBase, 32768);
  705.  
  706.     CallGeneratedCode(gCodeBase+4, xP, yP, nP,
  707.                       &nFloatValues, w,
  708.                       gConstants, gFunctions,
  709.                       2.718281828459, 3.1415926535898);
  710.  
  711.     //
  712.     //    Free up the memory we allocated.
  713.     //
  714.     DisposePtr((Ptr) gCodeBase);
  715.     gCodeBase = NULL;
  716.     gNextInstruction = NULL;
  717.     FreeTree(root);
  718.     if (gConstants) {
  719.         DisposePtr((Ptr) gConstants);
  720.         gConstants = NULL;
  721.     }
  722. }
  723.